def quick_sort(arr):
    """
    快速排序算法 - 基础版本
    时间复杂度: 平均O(nlogn)，最坏O(n²)
    空间复杂度: O(logn)
    """
    if len(arr) <= 1:
        return arr
    
    pivot = arr[len(arr) // 2]  # 选择中间元素作为基准
    left = [x for x in arr if   x < pivot]  # 小于基准的元素
    middle = [x for x in arr if x == pivot]  # 等于基准的元素
    right = [x for x  in arr if x > pivot]  # 大于基准的元素
    
    return quick_sort(left) + middle + quick_sort(right)


def quick_sort_inplace(arr, low=None, high=None):
    """
    快速排序算法 - 原地排序版本（节省空间）
    时间复杂度: 平均O(nlogn)，最坏O(n²)
    空间复杂度: O(logn)
    """ 
    if low is None:
        low = 0
    if high is None:
        high = len(arr) - 1
    
    if low < high:
        # 获取分区点
        pivot_index = partition(arr, low, high)
        # 递归排序左半部分
        quick_sort_inplace(arr, low, pivot_index - 1)
        # 递归排序右半部分
        quick_sort_inplace(arr, pivot_index + 1, high)
    
    return arr


def partition(arr, low, high):
    """
    分区函数 - 将数组分为两部分，左边小于基准，右边大于基准
    返回基准元素的最终位置
    """
    # 选择最右边的元素作为基准
    pivot = arr[high]
    # i 指向小于基准区域的最后一个位置
    i = low - 1
    
    # 遍历数组，将小于基准的元素移到左边
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    
    # 将基准元素放到正确位置
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1


def quick_sort_optimized(arr):
    """
    快速排序算法 - 优化版本
    使用三数取中法选择基准，减少最坏情况的发生
    """
    if len(arr) <= 1:
        return arr
    
    # 三数取中法选择基准
    def median_of_three(arr, low, high):
        mid = (low + high) // 2
        if arr[low] > arr[mid]:
            arr[low], arr[mid] = arr[mid], arr[low]
        if arr[low] > arr[high]:
            arr[low], arr[high] = arr[high], arr[low]
        if arr[mid] > arr[high]:
            arr[mid], arr[high] = arr[high], arr[mid]
        return arr[mid]
    
    def quick_sort_helper(arr, low, high):
        if low < high:
            # 选择基准
            pivot = median_of_three(arr, low, high)
            # 将基准移到倒数第二个位置
            arr[high-1], arr[(low + high) // 2] = arr[(low + high) // 2], arr[high-1]
            
            # 分区
            i = low
            j = high - 1
            while True:
                i += 1
                while arr[i] < pivot:
                    i += 1
                j -= 1
                while arr[j] > pivot:
                    j -= 1
                if i < j:
                    arr[i], arr[j] = arr[j], arr[i]
                else:
                    break
            
            # 将基准放到正确位置
            arr[i], arr[high-1] = arr[high-1], arr[i]
            
            # 递归排序
            quick_sort_helper(arr, low, i - 1)
            quick_sort_helper(arr, i + 1, high)
    
    quick_sort_helper(arr, 0, len(arr) - 1)
    return arr


def quick_sort_with_comparison(arr, key=None, reverse=False):
    """
    快速排序算法 - 支持自定义比较函数
    可以按照对象的某个属性排序
    """
    if len(arr) <= 1:
        return arr
    
    if key is None:
        key = lambda x: x
    
    pivot = arr[len(arr) // 2]
    pivot_key = key(pivot)
    
    left = [x for x in arr if key(x) < pivot_key]
    middle = [x for x in arr if key(x) == pivot_key]
    right = [x for x in arr if key(x) > pivot_key]
    
    result = quick_sort_with_comparison(left, key, reverse) + middle + quick_sort_with_comparison(right, key, reverse)
    
    if reverse:
        result.reverse()
    
    return result


# 测试代码
if __name__ == "__main__":
    # 测试用例
    test_cases = [
        [64, 34, 25, 12, 22, 11, 90],
        [5, 2, 4, 6, 1, 3],
        [1],
        [],
        [3, 3, 3, 3],
        [9, 8, 7, 6, 5, 4, 3, 2, 1],
        [1, 2, 3, 4, 5]  # 已排序
    ]
    
    print("快速排序测试:")
    print("=" * 60)
    
    for i, test_arr in enumerate(test_cases, 1):
        print(f"测试用例 {i}:")
        print(f"原始数组: {test_arr}")
        
        # 测试基础版本
        sorted_arr1 = quick_sort(test_arr.copy())
        print(f"基础版本: {sorted_arr1}")
        
        # 测试原地排序版本
        sorted_arr2 = quick_sort_inplace(test_arr.copy())
        print(f"原地排序: {sorted_arr2}")
        
        # 测试优化版本
        sorted_arr3 = quick_sort_optimized(test_arr.copy())
        print(f"优化版本: {sorted_arr3}")
        print()
    
    print("自定义比较函数测试:")
    print("=" * 60)
    
    # 测试自定义比较函数
    students = [
        {'name': 'Alice', 'age': 20, 'score': 85},
        {'name': 'Bob', 'age': 19, 'score': 92},
        {'name': 'Charlie', 'age': 21, 'score': 78},
        {'name': 'David', 'age': 20, 'score': 88}
    ]
    
    print("按年龄排序:")
    sorted_by_age = quick_sort_with_comparison(students.copy(), key=lambda x: x['age'])
    for student in sorted_by_age:
        print(f"  {student}")
    
    print("\n按分数排序（降序）:")
    sorted_by_score = quick_sort_with_comparison(students.copy(), key=lambda x: x['score'], reverse=True)
    for student in sorted_by_score:
        print(f"  {student}")
    
    print("\n按姓名排序:")
    sorted_by_name = quick_sort_with_comparison(students.copy(), key=lambda x: x['name'])
    for student in sorted_by_name:
        print(f"  {student}")


# 性能测试
def performance_test():
    """
    性能测试函数
    """
    import random
    import time
    
    # 生成测试数据
    sizes = [100, 1000, 10000]
    
    for size in sizes:
        print(f"\n测试数组大小: {size}")
        print("-" * 40)
        
        # 生成随机数组
        arr = [random.randint(1, 1000) for _ in range(size)]
        
        # 测试基础版本
        start_time = time.time()
        quick_sort(arr.copy())
        end_time = time.time()
        print(f"基础版本耗时: {end_time - start_time:.4f}秒")
        
        # 测试原地排序版本
        start_time = time.time()
        quick_sort_inplace(arr.copy())
        end_time = time.time()
        print(f"原地排序耗时: {end_time - start_time:.4f}秒")
        
        # 测试优化版本
        start_time = time.time()
        quick_sort_optimized(arr.copy())
        end_time = time.time()
        print(f"优化版本耗时: {end_time - start_time:.4f}秒")


if __name__ == "__main__":
    # 运行性能测试
    performance_test() 